import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/4 8:51
 * @description 树状数组，动态维护序列前缀和
 * 简单求区间和，用「前缀和」
 * 多次将某个区间变成同一个数，用「线段树」
 * 其他情况，用「树状数组」
 */
public class Solution2 {
    private int[] tree;
    private int[] nums;

    public Solution2(int[] nums) {
        this.tree = new int[nums.length + 1];
        this.nums = nums;
        for (int i = 0; i < nums.length; i++) {
            add(i + 1, nums[i]);
        }
    }

    public void update(int index, int val) {
        add(index + 1, val - nums[index]);
        nums[index] = val;
    }

    public int sumRange(int left, int right) {
        return prefixSum(right + 1) - prefixSum(left);
    }

    /**
     * x的二进制表示中，最低为1所参与的贡献值，如 x = 1100, 那么 -x = 1..0100; x & -x  = 0100
     * @param x x
     * @return int
     */
    private int lowBit(int x) {
        return x & -x;
    }

    /**
     * 单点修改，把序列第index个数增加val
     * @param index
     * @param val
     */
    private void add(int index, int val) {
        while (index < tree.length) {
            tree[index] += val;
            index += lowBit(index);
        }
    }

    /**
     * 查询前index个元素的前缀和
     * @param index
     * @return
     */
    private int prefixSum(int index) {
        int sum = 0;
        while (index > 0) {
            sum += tree[index];
            index -= lowBit(index);
        }
        return sum;
    }

    public static void main(String[] args) {
        int[] nums = {1 , 3, 5};
        Solution2 solution2 = new Solution2(nums);
        solution2.update(1, 4);
        solution2.sumRange(0, 2);
    }
}
